package algorithm.search;

/**
 * 折半查找（二分查找）
 */
public class BinarySearch {
    public static void main(String[] args) {

    }

    /**
     * 折半查询算法，数据元素已经按升序排列
     * @param table 数组表
     * @param cobj 查找的对象
     * @param low 范围下界
     * @param high 范围上界
     * @return
     */
    public static int binarySearch(Comparable[] table, Comparable cobj, int low, int high){
        System.out.println("talbe："+table+" cobj:"+cobj);
        if(table!=null && cobj != null){
            while(low <= high ){
                int mid = (low+high)/2;
                System.out.println("mid:"+table[mid]+" low:"+low+" high:"+high);
                if(cobj.compareTo(table[mid]) == 0) {//对象比较大小
                    return mid;//查找成功
                }else {
                    System.out.println("compareTo:" + cobj.compareTo(table[mid]) +" "+table[mid]);
                    if (cobj.compareTo(table[mid]) < 0)//给定的对象小
                        high = mid - 1;//查找范围缩小到前半段
                    else
                        low = mid + 1;
                }
            }
        }
        return -1;
    }
    /**
     * 折半查找，查找全部数组
     */
    public static int binarySearch(Comparable[] table, Comparable cobj) {
        return binarySearch(table, cobj,0, table.length-1);
    }
}
